/*******************************************************************************
* FileName:         LinkList.cpp
* Author:           Your_Name
* Student Number:   3022206093
* Date:             2024/10.16 15：25：00
* Version:          v1.0
* Description:      数据结构实验 #2
*                   作业在这个文件中完成，需要补全LinkList类的实现，
*                   写明必要的注释
*******************************************************************************/

#include "LinkList.h"

// 构造函数
LinkList::LinkList() {
    head = new node;  // 创建头节点
    head->next = nullptr; // 头节点的next指针初始化为nullptr
    len = 0;          // 初始化链表长度为0
}

// 析构函数
LinkList::~LinkList() {
    node *p = head->next; // 从头节点的下一个节点开始遍历
    node *q;              // 用于保存当前节点
    while (p != nullptr) { // 遍历链表
        q = p;            // 保存当前节点
        p = p->next;     // 移动到下一个节点
        delete q;        // 删除当前节点
    }
    head->next = nullptr; // 清空头节点的next指针
    delete head;          // 删除头节点
    len = 0;              // 重置长度
}

// 获取链表长度
int LinkList::length() const {
    return len; // 返回链表的长度
}

// 获取指定位置的数据
int LinkList::getData(const int& location) const {
    if (location < 0 || location > len - 1) return -1; // 超出范围返回-1

    node* p = head->next; // 从头节点的下一个节点开始
    int k = 0;
    while (k < location) { // 遍历到指定位置
        p = p->next; // 移动到下一个节点
        k++;
    }
    int x = p->value; // 获取指定位置的值
    return x; // 返回值
}

// 插入元素
void LinkList::insert(const int& data, const int& location) {
    if (location < 0 || location > len) return; // 超出范围则返回

    node* p = head; // 从头节点开始
    int k = 0;
    while (k < location) { // 遍历到指定位置
        p = p->next; // 移动到下一个节点
        k++;
    }

    node* q; // 新节点
    q = new node; // 创建新节点
    q->value = data; // 设置新节点的值
    q->next = p->next; // 新节点的next指针指向当前节点的next
    p->next = q; // 当前节点的next指向新节点

    len++; // 增加链表长度
    return;
}

// 删除指定位置的元素
bool LinkList::remove(const int& location) {
    if (location < 0 || location >= len) return false; // 超出范围返回false，表示删除失败

    node* p = head; // 从头节点开始
    for (int i = 0; i < location; i++) p = p->next; // 遍历到指定位置的前一个节点
    node* q = p->next; // 要删除的节点
    p->next = q->next; // 跳过要删除的节点
    delete q; // 删除节点

    len--; // 减少链表长度
    return true; // 返回true表示删除成功
}

// 翻转链表
void LinkList::converse() {
    node* q = nullptr; // 前一个节点指针
    node* cur = head->next; // 当前节点指针
    
    while (cur != nullptr) { // 遍历链表
        node* p = cur->next; // 保存下一个节点
        cur->next = q; // 反转当前节点的next指针
        q = cur; // 移动前一个节点指针
        cur = p; // 移动到下一个节点
    }

    head->next = q; // 更新头节点的next指针为新的头节点
    return;
}

// 拼接另一个链表
void LinkList::append(const LinkList& append_list) {
    node* start = append_list.head->next; // 获取要拼接链表的头节点
    node* p = head; // 从当前链表的头节点开始
    while (p->next != nullptr) p = p->next; // 找到当前链表的尾节点
    while (start != nullptr) { // 遍历要拼接的链表
        node* temp = new node; // 创建新节点
        temp->value = start->value; // 设置新节点的值
        temp->next = nullptr; // 新节点的next指针为nullptr
        p->next = temp; // 将当前链表的尾节点的next指向新节点
        p = temp; // 更新当前链表的尾节点
        start = start->next; // 移动到要拼接链表的下一个节点
    }
    len += append_list.len; // 更新当前链表的长度
}
